package exhaust;

/**
 * 三个水桶等分8升水的问题
 * <pre>
 *     有三个容积分别为3升、5升、8升的水桶，其中容积为8升的水桶中装满了水。容积为3升和5升的水桶是空的。现在只使用三个水桶，如何做，可以将水等分为2份，每份4升。
 * </pre>
 * Created by donghongli on 2017-03-22.
 */
public class UniformWater {

    //倒水方案总次数
    private static int   count          = 0;
    //三个水桶的容量
    private static int[] backetCapacity = { 8, 3, 5 };

    public static void main(String[] args) {
        //初始状态三个水桶中水量状态
        Tree startStatus = new Tree(new int[] { 8, 0, 0 });
        searchResult(startStatus);
        System.out.println("总共有" + count + "种倒水方案。");
    }

    /**
     * 递归遍历倒水过程
     * @param status
     *
     */
    private static void searchResult(Tree status) {
        for (int i = 0; i < status.backet.length; i++) {
            for (int j = 0; j < status.backet.length; j++) {
                if (i == j || checkCanUniform(i, j, status)) {
                    continue;
                }
                int[] backets = status.backet.clone();
                //倒出水的量
                int waterNum = (backetCapacity[j] - backets[j]) > backets[i] ? backets[i]
                    : (backetCapacity[j] - backets[j]);
                backets[i] = backets[i] - waterNum;
                backets[j] = backets[j] + waterNum;
                Tree newStatus = new Tree(backets);
                newStatus.parent = status;
                if (checkIsParentHaveSameStatus(newStatus)) {
                    continue;
                }
                if (checkResult(newStatus)) {
                    return;
                }
                searchResult(newStatus);
            }
        }
    }

    private static boolean checkCanUniform(int i, int j, Tree startStatus) {
        if (startStatus.backet[i] == 0) {
            return true;//倒出水的桶不能为空桶
        }
        return startStatus.backet[j] == backetCapacity[j];
    }

    /**
     * 检查父节点或父父节点，是否已经有这个状态，避免死循环
     * @param status
     * @return
     */
    private static boolean checkIsParentHaveSameStatus(Tree status) {
        Tree parent = status.parent;
        while (parent != null) {
            if (status.backet[0] == parent.backet[0] && status.backet[1] == parent.backet[1]
                && status.backet[2] == parent.backet[2]) {
                return true;
            }
            parent = parent.parent;
        }
        return false;
    }

    /**
     * 检查当前状态，是否已经是结果，如果是结果，则打印倒水过程
     * @param status
     * @return
     */
    private static boolean checkResult(Tree status) {
        if (status.backet[0] == 4 && status.backet[1] == 0 && status.backet[2] == 4) {
            printResult(status);
            ++count;
            return true;
        }
        return false;
    }

    /**
     * 打印倒水过程状态
     * @param status
     */
    private static void printResult(Tree status) {
        while (status != null) {
            for (int i : status.backet) {
                System.out.print(i + ",");
            }
            status = status.parent;
            System.out.println();
        }
        System.out.println("---------------");
    }

    public static class Tree {
        //三个水桶中存水量
        public int[] backet;

        public Tree  parent;

        public Tree(int[] backet) {
            this.backet = backet;
        }

    }
}
